package com.leetcode.partition4;

/**
 * @author `RKC`
 * @date 2021/8/6 8:54
 */
public class LC342四的幂 {

    /**
     * 位运算：如果n & n - 1 == 0，n一定是2的幂，但不一定是4的幂；如果n & n - 1 != 0，n不是2的幂，更不会是4的幂
     * 因此，在判断2的幂的前提下还需要判断是否是4的幂
     * 对于任意一个4的幂的数n = 4^x = (3 + 1)^x = 3^x + 1，又因为(3^x + 1) % 3 = 1
     */
    public static boolean isPowerOfFour(int n) {
        if (n < 1) return false;
        return (n & n - 1) == 0 && n % 3 == 1;
    }

    public static void main(String[] args) {
        System.out.println(isPowerOfFour(8));
    }
}
